#include <string>
#include <vector>
using namespace std;

bool isPalindrome(const string &s, int left, int right) {
  if (left == right) {
    return true;
  }
  while (left < right) {
    if (s[left] != s[right])
      return false;
    left++;
    right--;
  }
  return true;
}

void backtrace(vector<vector<string>> &res, int cur, string &s,
               vector<string> &path) {
  int len = s.size();
  if (cur == len - 1) {
    res.push_back(path);
    return;
  }
  for (int i = cur; i < len; i++) {
    if (isPalindrome(s, cur, i)) {
      path.push_back(s.substr(cur, i - cur + 1));
      backtrace(res, i + 1, s, path);
      path.pop_back();
    }
  }
}

vector<vector<string>> partition(string s) {
  vector<vector<string>> res;
  vector<string> path;
  backtrace(res, 0, s, path);
  return res;
}